package leetcode.linked;

/**
 * 92. 反转链表 II
 * <p>
 * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 * <p>
 * 说明:
 * 1 ≤ m ≤ n ≤ 链表长度。
 * <p>
 * 示例:
 * <p>
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NULL
 * <p>
 * 通过次数53,066
 * 提交次数105,809
 * <p>
 * 分析：需要明确的界限 m n 的越界情况 合法性 比如m>n m n都<0 n>node.length
 * 需要找到 m前一个元素位置 ， m为当前元素  m.next 使得
 * 做不出来。。。。。  你当时咋这么菜 ,这都做不出来嘛, 该题需要仔细想想实现, 每一个节点的变化
 */
public class Solution92 {
    /**
     * 注意边界问题即可  left right 是实际的第几个元素,而不是位置 从1开始而不是从0开始
     *
     * @param head
     * @param left
     * @param right
     * @return
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 找到区间内的前驱结点和后继节点 left-1 right+1;
        ListNode dummyNode = new ListNode(-1, head);
        ListNode pre = dummyNode;
        // pre 节点为 left-1
        for (int n = 0; n < left - 1; n++) {
            pre = pre.next;
        }
        ListNode rightNode = pre;
        // 从 pre 再走 right - left + 1 步，来到 right 节点
        for (int n = 0; n < right - left + 1; n++) {
            rightNode = rightNode.next;
        }

        ListNode leftNode = pre.next;
        ListNode successor = rightNode.next;

        // 截断出 需要被反转的连表
        pre.next = null;
        rightNode.next = null;

        reverseListNode(leftNode);

        // 重新组装连表
        pre.next = rightNode;
        leftNode.next = successor;
        return dummyNode.next;
    }

    private void reverseListNode(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

    }

    public static void main(String[] args) {
        Solution92 solution92 = new Solution92();
        // 1->2->3->4->5->null
        ListNode listNode = solution92.reverseBetween(new ListNode(1, new ListNode(2, new ListNode(3,
                new ListNode(4, new ListNode(5, new ListNode(6, null)))))), 2, 4);
        System.out.println(listNode.toString());
    }
}

